import java.util.Arrays;
import java.util.List;

/**
 * 119. 杨辉三角 II
 * https://leetcode-cn.com/problems/pascals-triangle-ii/
 */
public class Solutions_119 {
    public static void main(String[] args) {
        int rowIndex = 3;  // output: {1, 3, 3, 1}

        List<Integer> result = getRow(rowIndex);
        System.out.println(result);
    }

    public static List<Integer> getRow(int rowIndex) {
        Integer[][] dp = generate(rowIndex + 1);
        // 获取第 rowIndex 行
        return Arrays.asList(dp[rowIndex]);
    }

    // 生成 rowIndex + 1 行杨辉三角
    public static Integer[][] generate(int row) {
        Integer[][] dp = new Integer[row][row];
        dp[0][0] = 1;
        for (int i = 1; i < row; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    // 第 1 位与最后 1 位
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                }
            }
        }
        return dp;
    }
}
